package com.summer.hundred;

import java.util.HashSet;
import java.util.Set;

public class ques5 {
    public static void main(String[] args) {
        String s = "babad";//dabab
        System.out.println(longestPalindrome(s));
    }
    public static String longestPalindrome(String s) {
    int n =s.length();
    if (s.length()<=1) return s;
    boolean[][] f = new boolean[n][n];
    int maxLength = 1;
    int st  = 0;

    for (int i = 0; i <n ; i++) {
        f[i][i] = true;
        }
    int max = 1;
    int start = 0;
        char[] c = s.toCharArray();
    for (int j = 1;j<n;j++){
        for (int i = 0;i<n-1&&i<j;i++){
            if (c[i]!=c[j]){
                f[i][j] = false;
            }else {
                if (j-i<3){
                    f[i][j] = true;
                }else {
                    System.out.println(f[i][j]);
                    f[i][j]=f[i+1][j-1];
                }
            }
            if (f[i][j]&&j-i+1>max){
                max = j-i+1;
                start = i;
            }
        }
    }

return s.substring(start,start+max);
    }
}


